
  struct ListNode {
      int val;
      ListNode *next;
     ListNode() : val(0), next(nullptr) {}
      ListNode(int x) : val(x), next(nullptr) {}
      ListNode(int x, ListNode *next) : val(x), next(next) {}
  };

class Solution {
	
public:
    ListNode* insertionSortList(ListNode* head) {
        
        if(nullptr==head){
			
			return head;
		}
        ListNode preHead;
        preHead.next=head;
        ListNode* cur=head->next;
        ListNode* pre=head;
        while(cur){
			
			if(pre->val>cur->val){
				
				ListNode* tmp=&preHead;
				while(tmp->next->val<=cur->val){
					
					tmp=tmp->next;
				}
				pre->next=cur->next;
				cur->next=tmp->next;
				tmp->next=cur;	
				cur=pre->next;		
			}
			else{
				
				pre=pre->next;
				cur=cur->next;
			}
			
		}
		return preHead.next;
    }
};
